package baseclass.j_dp.dp.oneZeroBag;

import java.util.Arrays;

/**
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。
 * 现在你有两个符号 + 和 -。对于数组中的任意一个整数，
 * 你都可以从 + 或 -中选择一个符号添加在前面。
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 * 示例 1:
 * 输入: nums: [1, 1, 1, 1, 1], S: 3
 * 输出: 5 解释:
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 * 一共有5种方法让最终目标和为3。
 * 注意:
 * 数组非空，且长度不会超过20。
 * 初始的数组的和不会超过1000。
 * 保证返回的最终结果能被32位整数存下。
 *
 * @date 2020/3/2 21:25
 */
public class Code05_SumTargetCountInArr2 {
    /**
     * 方式1：暴力递归
     */

    public static int process1(int[] nums, int sum, int index) {
        if (index >= nums.length) {
            return sum == 0 ? 1 : 0;
        }
        //当前位置或正或负
        return process1(nums, sum - nums[index], index + 1)
                + process1(nums, sum + nums[index], index + 1);
    }

    public static int process2(int[] nums, int aim) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0;
        for (int e : nums) sum += e;
        if (Math.abs(aim) > sum) return 0;
        //
        int[][] memo = new int[nums.length][2*MAX_SUM+1];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i],-1);
        }
        return doProcess2(nums,aim,0,memo);
    }
    private static int doProcess2(int[] nums, int sum, int index, int[][] memo) {
        if (index >= nums.length) {
            return sum == 0 ? 1 : 0;
        }
        if(memo[index][MAX_SUM+sum] != -1) return memo[index][MAX_SUM+sum];
        //当前位置或正或负
        return memo[index][MAX_SUM+sum] =
                doProcess2(nums, sum - nums[index], index + 1, memo)
                + doProcess2(nums, sum + nums[index], index + 1, memo);
    }

    /**
     * 方式3：DP1。dp[i][j]表示决策完第i号元素后，当前和为j的种数
     * 因为任何元素必须是算进去，要么取正要么取负，所以：
     * 状态转移方程：dp[i][j] = dp[i-1][j-arr[i]] + dp[i-1][j+arr[i]]
     */
    private static final int MAX_SUM = 1000;

    public static int process3(int[] nums, int aim) {
        if (nums == null || nums.length == 0) return 0;
        //题目说最大sum是1000，那么范围就是-1000 - 1000
        int[][] dp = new int[nums.length][2 * MAX_SUM + 1];
        dp[0][MAX_SUM + nums[0]] = 1;
        dp[0][MAX_SUM - nums[0]] += 1; //注意这里要用 +，因为可能 nums[0]=0
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= 2*MAX_SUM; j++) {
                //dp[i][j] = dp[i-1][j-arr[i]] + dp[i-1][j+arr[i]]
                if (j - nums[i] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i]];
                }
                if (j + nums[i] <= 2 * MAX_SUM) {
                    dp[i][j] += dp[i - 1][j + nums[i]];
                }
            }
        }
        return dp[nums.length-1][MAX_SUM + aim];
    }

    /**
     * 方式3的空间优化2。
     * <p>
     * 由于转移方程为 dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];
     * <p>
     * 所以无法优化到只用一个一维数组，因为无论正序还是逆序遍历，都会被影响。
     * <p>
     * 可以优化到用两个一维数组。
     */
    private static int process4(int[] nums, int S) {
        if(nums == null || nums.length == 0)return 0;
        int number = nums.length - 1;
        //和范围是 -1000,1000，总共2001个
        int[][] dp = new int[2][2 * MAX_SUM + 1];
        //初始化0号位置的元素
        dp[0][MAX_SUM + nums[0]] = 1;
        //注意要考虑nums[0]= 0，那么要0和都不要0都是0，但是是两种选择所以这里是 +=
        dp[0][MAX_SUM - nums[0]] += 1;
        int row = 0;
        //从1号元素开始dp
        for (int i = 1; i <= number; i++) {
            //row交替0,1
            row = 1 - row;
            for (int j = 0; j <= 2 * MAX_SUM; j++) {
//                dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]];
                if (j - nums[i] >= 0) {
                    dp[row][j] = dp[1 - row][j - nums[i]];
                }
                if (j + nums[i] <= 2 * MAX_SUM) {
                    dp[row][j] += dp[1 - row][j + nums[i]];
                }
            }
        }
        return dp[row][S + MAX_SUM];
    }



    /**
     * 方式4：设集合为Q，目标为S。
     * <p>
     * 最终S是由集合P取正和集合Q取负组成，即 S = P - Q
     * <p>
     * P + Q + P-Q = sum + S = 2P,
     * <p>
     * 从而化简成在集合Q中寻找是否能组成 P = (sum+S)/2的 0-1背包问题
     */
    private static int process5(int[] nums, int S) {
        if(nums == null || nums.length == 0)return 0;
        int sum = 0;
        for (int num : nums) sum += num;
        if(S > sum) return 0;
        if ((sum + S) % 2 == 1) return 0;
        int target = (sum + S) / 2;
        //寻找和为target的数量
        int[][] dp = new int[nums.length][target + 1];
        //第0位置可以组成 0或nums[0]
        dp[0][0] = 1;
        //注意要判断
        if(nums[0] <= target)
            //注意要考虑nums[0]= 0，要0和不要0都是0但是是两种选择，所以这里是 +=
            dp[0][nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i])
                    dp[i][j] += dp[i-1][j-nums[i]];

            }
        }
        return dp[nums.length-1][target];
    }

    /**
     * 方式5的空间优化
     */
    private static int process6(int[] nums, int S) {
        if(nums == null || nums.length == 0)return 0;
        int sum = 0;
        for (int num : nums) sum += num;
        if ((sum + S) % 2 == 1) return 0;
        int target = (sum + S) / 2;
        //寻找和为target的数量
        int[] dp = new int[target + 1];
        dp[0] = 1;
        //注意要考虑nums[0]= 0，要0和不要0都是0但是是两种选择，所以这里是 +=
        if(nums[0] <= target)
            dp[nums[0]] += 1;
        for (int i = 1; i < nums.length; i++) {
            //对j逆序更新，不会影响结果。正序会影响结果,变成完全背包
            for (int j = target; j >= nums[i]; j--) {
                //dp[j] = 当前num不要 + 当前num要 = dp[j] + dp[j - nums[i]]
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }
        return dp[target];
    }
    public static void main(String[] args) {
        int[] arr = {15, 2, 4};
        System.out.println(process1(arr, 10, 0));
        System.out.println(process2(arr, 10));
        System.out.println(process3(arr, 10));

        for (int i = 0; i < 100000; i++) {
            arr = generateRandomArray(10, 20);
            int aim = (int) (Math.random() * 21);
            try {
                if (process4(arr, aim) != process6(arr, aim)) {
                    System.out.println("出错的数组:" + Arrays.toString(arr));
                    System.out.println(aim);
                    break;
                }
            } catch (Exception e) {
                e.printStackTrace();
                System.out.println(Arrays.toString(arr));
                break;
            }

        }
    }

    // for test
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        //产生 [0-maxsize]随机长度的数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            //随机产生数据
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

}
